/**
 * 多数元素
 * https://leetcode.cn/problems/majority-element
 */

/**
 * 方法一：哈希表
 * 键key是此元素的值，值value是此元素出现的次数
 * 时间复杂度：O(n)
 * 空间复杂度：O(n)
 * @param {*} nums 
 */
const majorityElement = function(nums) {
    const map = new Map(); // 新建Map
    for (const num of nums) { // 遍历数组
        if (map.has(num)) { // 如果Map中有此元素
            map.set(num, map.get(num) + 1); // 值+1
        } else {
            map.set(num, 1); // 如果Map中没有此元素，新增
        }
    }
    for (const [key, value] of map) { // 遍历Map
        if (value > nums.length / 2) { // 如果值大于数组长度的一半
            return key; // 返回此元素
        }
    }
}

/**
 * 方法二：排序
 * 排序后，中间的元素一定是出现次数大于数组长度一半的元素
 * 时间复杂度：O(nlogn)
 * 空间复杂度：O(logn)
 */
const majorityElement2 = function(nums) {
    nums.sort((a, b) => a - b); // 排序
    return nums[Math.floor(nums.length / 2)];
}
